// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
)

// 基数排序
func radixSort(array []int) []int {
	largestNum := findLargestNum(array)
	size := len(array)
	significantDigit := 1
	semiSorted := make([]int, size, size)

	// 循环直到到达最大的有效数字
	for largestNum/significantDigit > 0 {
		//整数是十进制数，因此定义一个数量为10的数组
		bucket := [10]int{0}

		// 计算将进入每个桶的键或数字的数量
		for i := 0; i < size; i++ {
			bucket[(array[i]/significantDigit)%10]++
		}

		// 添加前一个桶的计数
		// 获取数组中每个桶位置结束后的索引
		// 类似于计数排序算法
		for i := 1; i < 10; i++ {
			bucket[i] += bucket[i-1]
		}

		// 使用桶填充一个名为semiSorted的数组
		for i := size - 1; i >= 0; i-- {
			bucket[(array[i]/significantDigit)%10]--
			semiSorted[bucket[(array[i]/significantDigit)%10]] = array[i]
		}

		for i := 0; i < size; i++ {
			array[i] = semiSorted[i]
		}

		significantDigit *= 10
	}

	return array
}

// 查找数组中最大的数
func findLargestNum(array []int) int {
	largestNum := 0

	for i := 0; i < len(array); i++ {
		if array[i] > largestNum {
			largestNum = array[i]
		}
	}
	return largestNum
}

func main() {
	array := []int{33, 23, 56, 7, 8, 18, 99, 28}
	res := radixSort(array)
	fmt.Println(res)
}

//$ go run radixSort.go
//[7 8 18 23 28 33 56 99]
